package com.example.zzy.zzytest.algo.sort.bucket;

/**
 * 计数排序
 * 要求输入的数据必须是有确定范围的整数
 * 如果数据范围小，可以用
 */
public class CountSort {
    public static void main(String[] args) {
        //如果有负数的话，还需要找最小值，图方便这里只有正数
        int[] testArr = new int[]{7, 8, 0, 2, 6, 3};
        int maxInt = getMaxInt(testArr);

        int[] sorted = countSort(testArr, maxInt);
        for (int i : sorted) {
            System.out.print(i + " ");
        }
    }

    private static int[] countSort(int[] arr, int maxInt) {
        int bucketLen = maxInt + 1;
        int[] bucket = new int[bucketLen];
        for (int value : arr) {
            bucket[value]++;
        }

        int index = 0;
        for (int j = 0; j < bucketLen; j++) {
            if (bucket[j] > 0) {
                arr[index++] = j;
                bucket[j]--;
            }
        }

        return arr;
    }

    private static int getMaxInt(int[] arr) {
        int max = arr[0];
        for (int i : arr) {
            if (i > max) {
                max = i;
            }
        }
        return max;
    }
}
